<!DOCTYPE HTML>
<html lang="en" class="light" dir="ltr">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>PISA Guide</title>
        <meta name="robots" content="noindex">


        <!-- Custom HTML head -->
        
        <meta name="description" content="">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff">

        <link rel="icon" href="favicon.svg">
        <link rel="shortcut icon" href="favicon.png">
        <link rel="stylesheet" href="css/variables.css">
        <link rel="stylesheet" href="css/general.css">
        <link rel="stylesheet" href="css/chrome.css">
        <link rel="stylesheet" href="css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="highlight.css">
        <link rel="stylesheet" href="tomorrow-night.css">
        <link rel="stylesheet" href="ayu-highlight.css">

        <!-- Custom theme stylesheets -->

    </head>
    <body class="sidebar-visible no-js">
    <div id="body-container">
        <!-- Provide site root to javascript -->
        <script>
            var path_to_root = "";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script>
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script>
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('light')
            html.classList.add(theme);
            var body = document.querySelector('body');
            body.classList.remove('no-js')
            body.classList.add('js');
        </script>

        <input type="checkbox" id="sidebar-toggle-anchor" class="hidden">

        <!-- Hide / unhide sidebar before it is displayed -->
        <script>
            var body = document.querySelector('body');
            var sidebar = null;
            var sidebar_toggle = document.getElementById("sidebar-toggle-anchor");
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            } else {
                sidebar = 'hidden';
            }
            sidebar_toggle.checked = sidebar === 'visible';
            body.classList.remove('sidebar-visible');
            body.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded affix "><a href="introduction.html">Introduction</a></li><li class="chapter-item expanded affix "><li class="part-title">User Guide</li><li class="chapter-item expanded "><a href="guide/requirements.html"><strong aria-hidden="true">1.</strong> Requirements</a></li><li class="chapter-item expanded "><a href="guide/installation.html"><strong aria-hidden="true">2.</strong> Installation</a></li><li class="chapter-item expanded "><a href="guide/indexing-pipeline.html"><strong aria-hidden="true">3.</strong> Indexing Pipeline</a></li><li class="chapter-item expanded "><a href="guide/parsing.html"><strong aria-hidden="true">4.</strong> Parsing</a></li><li class="chapter-item expanded "><a href="guide/inverting.html"><strong aria-hidden="true">5.</strong> Inverting</a></li><li class="chapter-item expanded "><a href="guide/compressing.html"><strong aria-hidden="true">6.</strong> Compressing</a></li><li class="chapter-item expanded "><a href="guide/wand_data.html"><strong aria-hidden="true">7.</strong> "WAND" Data</a></li><li class="chapter-item expanded "><a href="guide/querying.html"><strong aria-hidden="true">8.</strong> Querying</a></li><li class="chapter-item expanded "><a href="guide/algorithms.html"><strong aria-hidden="true">9.</strong> Retrieval Algorithms</a></li><li class="chapter-item expanded "><a href="guide/reordering.html"><strong aria-hidden="true">10.</strong> Document Reordering</a></li><li class="chapter-item expanded "><a href="guide/sharding.html"><strong aria-hidden="true">11.</strong> Sharding</a></li><li class="chapter-item expanded "><a href="guide/threshold-estimation.html"><strong aria-hidden="true">12.</strong> Threshold Estimation</a></li><li class="chapter-item expanded affix "><li class="part-title">Tutorials</li><li class="chapter-item expanded "><a href="tutorial/robust04.html"><strong aria-hidden="true">13.</strong> Regression test for Robust04</a></li><li class="chapter-item expanded affix "><li class="part-title">CLI Reference</li><li class="chapter-item expanded "><a href="cli/compress_inverted_index.html"><strong aria-hidden="true">14.</strong> compress_inverted_index</a></li><li class="chapter-item expanded "><a href="cli/compute_intersection.html"><strong aria-hidden="true">15.</strong> compute_intersection</a></li><li class="chapter-item expanded "><a href="cli/count-postings.html"><strong aria-hidden="true">16.</strong> count-postings</a></li><li class="chapter-item expanded "><a href="cli/create_wand_data.html"><strong aria-hidden="true">17.</strong> create_wand_data</a></li><li class="chapter-item expanded "><a href="cli/evaluate_queries.html"><strong aria-hidden="true">18.</strong> evaluate_queries</a></li><li class="chapter-item expanded "><a href="cli/extract-maxscores.html"><strong aria-hidden="true">19.</strong> extract-maxscores</a></li><li class="chapter-item expanded "><a href="cli/extract_topics.html"><strong aria-hidden="true">20.</strong> extract_topics</a></li><li class="chapter-item expanded "><a href="cli/invert.html"><strong aria-hidden="true">21.</strong> invert</a></li><li class="chapter-item expanded "><a href="cli/kth_threshold.html"><strong aria-hidden="true">22.</strong> kth_threshold</a></li><li class="chapter-item expanded "><a href="cli/lexicon.html"><strong aria-hidden="true">23.</strong> lexicon</a></li><li class="chapter-item expanded "><a href="cli/map_queries.html"><strong aria-hidden="true">24.</strong> map_queries</a></li><li class="chapter-item expanded "><a href="cli/parse_collection.html"><strong aria-hidden="true">25.</strong> parse_collection</a></li><li class="chapter-item expanded "><a href="cli/partition_fwd_index.html"><strong aria-hidden="true">26.</strong> partition_fwd_index</a></li><li class="chapter-item expanded "><a href="cli/queries.html"><strong aria-hidden="true">27.</strong> queries</a></li><li class="chapter-item expanded "><a href="cli/read_collection.html"><strong aria-hidden="true">28.</strong> read_collection</a></li><li class="chapter-item expanded "><a href="cli/reorder-docids.html"><strong aria-hidden="true">29.</strong> reorder-docids</a></li><li class="chapter-item expanded "><a href="cli/sample_inverted_index.html"><strong aria-hidden="true">30.</strong> sample_inverted_index</a></li><li class="chapter-item expanded "><a href="cli/selective_queries.html"><strong aria-hidden="true">31.</strong> selective_queries</a></li><li class="chapter-item expanded "><a href="cli/shards.html"><strong aria-hidden="true">32.</strong> shards</a></li><li class="chapter-item expanded "><a href="cli/stem_queries.html"><strong aria-hidden="true">33.</strong> stem_queries</a></li><li class="chapter-item expanded "><a href="cli/taily-stats.html"><strong aria-hidden="true">34.</strong> taily-stats</a></li><li class="chapter-item expanded "><a href="cli/taily-thresholds.html"><strong aria-hidden="true">35.</strong> taily-thresholds</a></li><li class="chapter-item expanded "><a href="cli/thresholds.html"><strong aria-hidden="true">36.</strong> thresholds</a></li><li class="chapter-item expanded affix "><li class="part-title">Specifications</li><li class="chapter-item expanded "><a href="specs/lookup-table.html"><strong aria-hidden="true">37.</strong> Lookup Table</a></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <!-- Track and set sidebar scroll position -->
        <script>
            var sidebarScrollbox = document.querySelector('#sidebar .sidebar-scrollbox');
            sidebarScrollbox.addEventListener('click', function(e) {
                if (e.target.tagName === 'A') {
                    sessionStorage.setItem('sidebar-scroll', sidebarScrollbox.scrollTop);
                }
            }, { passive: true });
            var sidebarScrollTop = sessionStorage.getItem('sidebar-scroll');
            sessionStorage.removeItem('sidebar-scroll');
            if (sidebarScrollTop) {
                // preserve sidebar scroll position when navigating via links within sidebar
                sidebarScrollbox.scrollTop = sidebarScrollTop;
            } else {
                // scroll sidebar to current active section when navigating via "next/previous chapter" buttons
                var activeSection = document.querySelector('#sidebar .active');
                if (activeSection) {
                    activeSection.scrollIntoView({ block: 'center' });
                }
            }
        </script>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky">
                    <div class="left-buttons">
                        <label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </label>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">PISA Guide</h1>

                    <div class="right-buttons">
                        <a href="print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script>
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="introduction"><a class="header" href="#introduction">Introduction</a></h1>
<p>PISA is a text search engine able to run on large-scale collections of
documents. It allows researchers to experiment with state-of-the-art
techniques, allowing an ideal environment for rapid development.</p>
<p>Some features of PISA are listed below:</p>
<ul>
<li>Written in C++ for performance</li>
<li>Indexing, parsing &amp; sharding capabilities</li>
<li>Many index compression methods supported</li>
<li>Many query processing algorithms supported</li>
<li>Implementation of document reordering</li>
<li>Free and open-source with permissive license</li>
</ul>
<h2 id="note"><a class="header" href="#note">Note</a></h2>
<p>PISA is still in its unstable release, and no stability or
backwards-compatibility is guaranteed with each new version. New
features are constantly added, and contributions are welcome!</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="requirements"><a class="header" href="#requirements">Requirements</a></h1>
<h2 id="compilers"><a class="header" href="#compilers">Compilers</a></h2>
<p>To compile PISA, you will need a compiler supporting the C++20 standard.
Our continuous integration pipeline compiles PISA and runs tests in the
following configurations:</p>
<ul>
<li>Linux:
<ul>
<li>GCC, versions: 10, 11, 12, 13, 14</li>
<li>Clang 16, 17, 18, 19</li>
</ul>
</li>
</ul>
<p>There are currently no MacOS builds running in CI because we have no one
actively maintaining them. That said, Mac builds should in theory work
on the x86 architecture. The new ARM-based architecture has not been
tested.</p>
<p><em>Supporting Windows is planned but is currently not being actively
worked on</em>, mostly due to a combination of man-hour shortage,
prioritization, and no core contributors working on Windows at the
moment. If you want to help us set up a Github workflow for Windows and
work out some issues with compilation, let us know on our <a href="https://join.slack.com/t/pisa-engine/shared_invite/zt-dbxrm1mf-RtQMZTqxxlhOJsv3GHUErw">Slack
channel</a>.</p>
<h2 id="system-dependencies"><a class="header" href="#system-dependencies">System Dependencies</a></h2>
<p>Most build dependencies are managed automatically with CMake and git submodules.
However, several dependencies still need to be manually provided:</p>
<ul>
<li><code>CMake &gt;= 3.0</code></li>
<li><code>autoconf</code>,  <code>automake</code>, <code>libtool</code>, and <code>m4</code> (for building <code>gumbo-parser</code>)</li>
<li>OpenMP (optional)</li>
</ul>
<p>You can opt in to use some system dependencies instead of those in git
submodules:</p>
<ul>
<li><a href="https://github.com/google/benchmark">Google Benchmark</a>
(<code>PISA_SYSTEM_GOOGLE_BENCHMARK</code>): this is a dependency used only for
compiling and running microbenchmarks.</li>
<li><a href="https://github.com/oneapi-src/oneTBB">oneTBB</a> (<code>PISA_SYSTEM_ONETBB</code>):
both build-time and runtime dependency.</li>
<li><a href="https://www.boost.org/">Boost</a> (<code>PISA_SYSTEM_BOOST</code>): both build-time
and runtime dependency.</li>
<li><a href="https://github.com/CLIUtils/CLI11">CLI11</a> (<code>PISA_SYSTEM_CLI11</code>):
build-time only dependency used in command line tools.</li>
</ul>
<p>For example, to use all the system installation of Boost in your build:</p>
<pre><code>cmake -DPISA_SYSTEM_BOOST=ON &lt;source-dir&gt;
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="installation"><a class="header" href="#installation">Installation</a></h1>
<p>The following steps explain how to build PISA.
First, you need the code checked out from Github.
(Alternatively, you can download the tarball and unpack it on your local machine.)</p>
<pre><code class="language-shell">$ git clone https://github.com/pisa-engine/pisa.git
$ cd pisa
</code></pre>
<p>Then create a build environment.</p>
<pre><code class="language-shell">$ mkdir build
$ cd build
</code></pre>
<p>Finally, configure with CMake and compile:</p>
<pre><code class="language-shell">$ cmake ..
$ make
</code></pre>
<h2 id="build-types"><a class="header" href="#build-types">Build Types</a></h2>
<p>There are two build types available:</p>
<ul>
<li><code>Release</code> (default)</li>
<li><code>Debug</code></li>
<li><code>RelWithDebInfo</code></li>
<li><code>MinSizeRel</code></li>
</ul>
<p>Use <code>Debug</code> only for development, testing, and debugging. It is much slower at runtime.</p>
<p>Learn more from <a href="https://cmake.org/cmake/help/latest/variable/CMAKE_BUILD_TYPE.html">CMake documentation</a>.</p>
<h2 id="build-systems"><a class="header" href="#build-systems">Build Systems</a></h2>
<p>CMake supports configuring for different build systems.
On Linux and Mac, the default is Makefiles, thus, the following two commands are equivalent:</p>
<pre><code class="language-shell">$ cmake -G ..
$ cmake -G &quot;Unix Makefiles&quot; ..
</code></pre>
<p>Alternatively to Makefiles, you can configure the project to use Ninja instead:</p>
<pre><code class="language-shell">$ cmake -G Ninja ..
$ ninja # instead of make
</code></pre>
<p>Other build systems should work in theory but are not tested.</p>
<h2 id="testing"><a class="header" href="#testing">Testing</a></h2>
<p>You can run the unit and integration tests with:</p>
<pre><code class="language-shell">$ ctest
</code></pre>
<p>The directory <code>test/test_data</code> contains a small document collection used in the
unit tests. The binary format of the collection is described in a following
section.
An example set of queries can also be found in <code>test/test_data/queries</code>.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="indexing-pipeline"><a class="header" href="#indexing-pipeline">Indexing Pipeline</a></h1>
<p>This section is an overview of how to take a collection
to a state in which it can be queried.
This process is intentionally broken down into several steps,
with a bunch of independent tools performing different tasks.
This is because we want the flexibility of experimenting with each
individual step without recomputing the entire pipeline.</p>
<p><img src="guide/../pipeline.png" alt="Indexing Pipeline" /></p>
<h2 id="external-resources"><a class="header" href="#external-resources">External Resources</a></h2>
<h3 id="raw-collection"><a class="header" href="#raw-collection">Raw Collection</a></h3>
<p>The <em>raw collection</em> is a dataset containing the documents to index. A
collection is encoded in one of the <a href="guide/parsing.html#supported-formats">supported
formats</a> that stores a list of document
contents along with some metadata, such as URL and title. The
<code>parse_collection</code> tool takes a collection as an input and parses it to
a forward index (see <a href="guide/indexing-pipeline.html#forward-index">Forward Index</a>). See
<a href="guide/parsing.html">Parsing</a> for more details.</p>
<h3 id="ciff-index"><a class="header" href="#ciff-index">CIFF Index</a></h3>
<p>This is an inverted index in the <a href="https://github.com/osirrc/ciff">Common Index File Format</a>.
It can be converted to an uncompressed PISA index (more information below)
with the <a href="https://github.com/pisa-engine/ciff"><code>ciff2pisa</code></a> tool.</p>
<h2 id="forward-index"><a class="header" href="#forward-index">Forward Index</a></h2>
<p>A <em>forward index</em> is the output of the <code>parse_collection</code> tool.
It represents each document as a list of tokens (terms) in the order of their appearance.
To learn more about parsing and the forward index format, see <a href="guide/parsing.html">Parsing</a>.</p>
<h2 id="inverted-index"><a class="header" href="#inverted-index">Inverted Index</a></h2>
<p>An inverted index is the most fundamental structure in PISA.
For each term in the collection, it contains a list of documents the term appears in.
PISA distinguishes two types of inverted index.</p>
<h3 id="uncompressed--binary-collection"><a class="header" href="#uncompressed--binary-collection">Uncompressed / Binary Collection</a></h3>
<p>The uncompressed index stores document IDs and frequencies as 4-byte integers.
It is an intermediate format between forward index and compressed inverted index.
It is obtained by running <code>invert</code> on a forward index.
To learn more about inverting a forward index, see <a href="guide/inverting.html">Inverting</a>.
Optionally, documents can be reordered with <code>reorder-docids</code> to obtain another
instance of uncompressed inverted index with different assignment of IDs to documents.
More on reordering can be found in <a href="guide/document_reordering.html">Document Reordering</a>.</p>
<h3 id="compressed"><a class="header" href="#compressed">Compressed</a></h3>
<p>An uncompressed index is large and therefore before running queries, it
must be compressed with one of many available encoding methods. It is
this compressed index format that is directly used when issuing queries.
See <a href="guide/compress-index.html">Compress Index</a> to learn more.</p>
<h2 id="wand-data"><a class="header" href="#wand-data">WAND Data</a></h2>
<p>This is a special metadata file containing additional statistics used during query processing.
See <a href="guide/query_index.html#build-additional-data">Build additional data</a>.</p>
<h2 id="shards"><a class="header" href="#shards">Shards</a></h2>
<p>PISA supports partitioning a forward index into subsets called <em>shards</em>.
Structures of all shards can be transformed in bulk using <code>shards</code> command line tool.
To learn more, read <a href="guide/sharding.html">Sharding</a>.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="parsing"><a class="header" href="#parsing">Parsing</a></h1>
<p>A <em>forward index</em> is a data structure that stores the term identifiers
associated to every document. Conversely, an <em>inverted index</em> stores for
each unique term the document identifiers where it appears (usually,
associated to a numeric value used for ranking purposes such as the raw
frequency of the term within the document).</p>
<p>The objective of the parsing process is to represent a given collection
as a forward index. To parse a collection, use the <code>parse_collection</code>
command, for example:</p>
<pre><code>$ mkdir -p path/to/forward
$ zcat ClueWeb09B/*/*.warc.gz | \   # pass unzipped stream in WARC format
    parse_collection \
    -j 8 \                          # use up to 8 threads at a time
    -b 10000 \                      # one thread builds up to 10k documents in memory
    -f warc \                       # use WARC
    -F lowercase porter2 \          # lowercase and stem every term (using the Porter2 algorithm)
    --html \                        # strip HTML markup before extracting tokens
    -o path/to/forward/cw09b
</code></pre>
<p>In case you get the error <code>-bash: /bin/zcat: Argument list too long</code>,
you can pass the unzipped stream using:</p>
<pre><code>$ find ClueWeb09B -name '*.warc.gz' -exec zcat -q {} \;
</code></pre>
<p>The parsing process will write the following files:</p>
<ul>
<li><code>cw09b</code>: forward index in binary format.</li>
<li><code>cw09b.terms</code>: a new-line-delimited list of sorted terms, where term
having ID N is on line N, with N starting from 0.</li>
<li><code>cw09b.termlex</code>: a binary representation (lexicon) of the <code>.terms</code>
file that is used to look up term identifiers at query time.</li>
<li><code>cw09b.documents</code>: a new-line-delimited list of document titles (e.g.,
TREC-IDs), where document having ID N is on line N, with N starting
from 0.</li>
<li><code>cw09b.doclex</code>: a binary representation of the <code>.documents</code> file that
is used to look up document identifiers at query time.</li>
<li><code>cw09b.urls</code>: a new-line-delimited list of URLs, where URL having ID N
is on line N, with N starting from 0. Also, keep in mind that each ID
corresponds with an ID of the <code>cw09b.documents</code> file.</li>
</ul>
<h2 id="generating-mapping-files"><a class="header" href="#generating-mapping-files">Generating mapping files</a></h2>
<p>Once the forward index has been generated, a binary document map and
lexicon file will be automatically built. However, they can also be
built using the <code>lexicon</code> utility by providing the new-line delimited
file as input. The <code>lexicon</code> utility also allows efficient look-ups and
dumping of these binary mapping files.</p>
<p>For example, assume we have the following plaintext, new-line delimited
file, <code>example.terms</code>:</p>
<pre><code>    aaa
    bbb
    def
    zzz
</code></pre>
<p>We can generate a lexicon as follows:</p>
<pre><code>./bin/lexicon build example.terms example.lex
</code></pre>
<p>You can dump the binary lexicon back to a plaintext representation:</p>
<pre><code>./bin/lexicon print example.lex
</code></pre>
<p>It should output:</p>
<pre><code>    aaa
    bbb
    def
    zzz
</code></pre>
<p>You can retrieve the term with a given identifier:</p>
<pre><code>./bin/lexicon lookup example.lex 2
</code></pre>
<p>Which outputs:</p>
<pre><code>def
</code></pre>
<p>Finally, you can retrieve the id of a given term:</p>
<pre><code>./bin/lexicon rlookup example.lex def
</code></pre>
<p>It outputs:</p>
<pre><code>2
</code></pre>
<p><em>NOTE</em>: This requires the initial file to be lexicographically sorted,
as <code>rlookup</code> uses binary search for reverse lookups.</p>
<h2 id="supported-stemmers"><a class="header" href="#supported-stemmers">Supported stemmers</a></h2>
<ul>
<li><a href="https://snowballstem.org/algorithms/english/stemmer.html">Porter2</a></li>
<li><a href="https://dl.acm.org/doi/abs/10.1145/160688.160718">Krovetz</a></li>
</ul>
<p>Both are English stemmers. Unfortunately, PISA does not have support for
any other languages. Contributions are welcome.</p>
<h2 id="supported-formats"><a class="header" href="#supported-formats">Supported formats</a></h2>
<p>The following raw collection formats are supported:</p>
<ul>
<li><code>plaintext</code>: every line contains the document's title first, then any
number of whitespaces, followed by the content delimited by a new line
character.</li>
<li><code>jsonl</code>: every line is a JSON document with three fields: <code>title</code>,
<code>content</code>, and (optionally) <code>url</code> (NOTE: &quot;title&quot; in PISA is a unique
string identifying a document)</li>
<li><code>trectext</code>: TREC newswire collections.</li>
<li><code>trecweb</code>: TREC web collections.</li>
<li><code>warc</code>: Web ARChive format as defined in <a href="https://iipc.github.io/warc-specifications/specifications/warc-format/warc-1.0/">the format
specification</a>.</li>
<li><code>wapo</code>: TREC Washington Post Corpus.</li>
</ul>
<p>In case you want to parse a set of files where each one is a document (for example, the collection
<a href="http://dg3rtljvitrle.cloudfront.net/wiki-large.tar.gz">wiki-large</a>), use the <code>files2trec.py</code> script
to format it to TREC (take into account that each relative file path is used as the document ID).
Once the file is generated, parse it with the <code>parse_collection</code> command specifying the <code>trectext</code>
value for the <code>--format</code> option.</p>
<h2 id="ir-datasets"><a class="header" href="#ir-datasets">IR Datasets</a></h2>
<p>We provide a convenient integration with
<a href="https://ir-datasets.com/">ir-datasets</a> through a Python script that can
be piped to the <code>parse_collection</code> tool.</p>
<p><strong>NOTE</strong>: the script depends on a Python 3 environment that has the
<code>ir-datasets</code> package already installed. See the project's documentation
for the installation instructions.</p>
<p>The script is called <code>ir-datasets</code> and is copied to the <code>bin</code> directory
when compiling the project. It takes one argument, which is the name of
the collection you want to parse. Please refer to
<a href="https://ir-datasets.com/">ir-datasets</a> for the list of supported
datasets and for the instructions on how to connect the datasets that
are not downloaded directly, but rather have to be linked manually.</p>
<p>The documents are printed to the standard output in the JSONL format.
You can pipe the output of the <code>ir-datasets</code> script to <code>parse_dataset</code>
program, and pass <code>--format jsonl</code> to the latter.</p>
<pre><code>$ ir-datasets wikir/en1k | \
    parse_collection -f jsonl -F lowercase porter2 -o path/to/forward/index
</code></pre>
<p>Note that the first run of the <code>ir-datasets</code> script on a given
collection may take a while because it may have to download the data to
the local drive first.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="inverting"><a class="header" href="#inverting">Inverting</a></h1>
<p>Once the parsing phase is complete, use the <code>invert</code> command to turn a
<em>forward index</em> into an <em>inverted index</em>. For example, assuming the
existence of a forward index in the path <code>path/to/forward/cw09b</code>:</p>
<pre><code>$ mkdir -p path/to/inverted
$ ./invert -i path/to/forward/cw09b \
    -o path/to/inverted/cw09b \
    --term-count `wc -w &lt; path/to/forward/cw09b.terms`
</code></pre>
<p>Note that the script requires as parameter the number of terms to be
indexed, which is obtained by embedding the
<code>wc -w &lt; path/to/forward/cw09b.terms</code> instruction.</p>
<h2 id="inverted-index-format"><a class="header" href="#inverted-index-format">Inverted index format</a></h2>
<p>A <em>binary sequence</em> is a sequence of integers prefixed by its length,
where both the sequence integers and the length are written as 32-bit
little-endian unsigned integers. An <em>inverted index</em> consists of 3
files, <code>&lt;basename&gt;.docs</code>, <code>&lt;basename&gt;.freqs</code>, <code>&lt;basename&gt;.sizes</code>:</p>
<ul>
<li>
<p><code>&lt;basename&gt;.docs</code> starts with a singleton binary sequence where its
only integer is the number of documents in the collection. It is then
followed by one binary sequence for each posting list, in order of
term-ids. Each posting list contains the sequence of document-ids
containing the term.</p>
</li>
<li>
<p><code>&lt;basename&gt;.freqs</code> is composed of a one binary sequence per posting
list, where each sequence contains the occurrence counts of the
postings, aligned with the previous file (note however that this file
does not have an additional singleton list at its beginning).</p>
</li>
<li>
<p><code>&lt;basename&gt;.sizes</code> is composed of a single binary sequence whose
length is the same as the number of documents in the collection, and
the i-th element of the sequence is the size (number of terms) of the
i-th document.</p>
</li>
</ul>
<h2 id="reading-the-inverted-index-using-python"><a class="header" href="#reading-the-inverted-index-using-python">Reading the inverted index using Python</a></h2>
<p>Here is an example of a Python script reading the uncompressed inverted
index format:</p>
<pre><code class="language-python">import os
import numpy as np

class InvertedIndex:
    def __init__(self, index_name):
        index_dir = os.path.join(index_name)
        self.docs = np.memmap(index_name + &quot;.docs&quot;, dtype=np.uint32,
              mode='r')
        self.freqs = np.memmap(index_name + &quot;.freqs&quot;, dtype=np.uint32,
              mode='r')

    def __iter__(self):
        i = 2
        while i &lt; len(self.docs):
            size = self.docs[i]
            yield (self.docs[i+1:size+i+1], self.freqs[i-1:size+i-1])
            i += size+1

    def __next__(self):
        return self

for i, (docs, freqs) in enumerate(InvertedIndex(&quot;cw09b&quot;)):
    print(i, docs, freqs)
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="compressing"><a class="header" href="#compressing">Compressing</a></h1>
<p>To create an index use the command <code>compress_inverted_index</code>. The
available index types are listed in <code>index_types.hpp</code>.</p>
<p>For example, to create an index using the optimal partitioning
algorithm, using the test collection, execute the command:</p>
<pre><code>$ ./bin/compress_inverted_index -t opt \
    -c ../test/test_data/test_collection \
    -o test_collection.index.opt \
    --check
</code></pre>
<p>where <code>test/test_data/test_collection</code> is the <em>basename</em> of the
collection, that is the name without the <code>.{docs,freqs,sizes}</code>
extensions, and <code>test_collection.index.opt</code> is the filename of the
output index. <code>--check</code> will trigger a verification step to check the
correctness of the index.</p>
<h2 id="compression-algorithms"><a class="header" href="#compression-algorithms">Compression Algorithms</a></h2>
<h3 id="binary-interpolative-coding"><a class="header" href="#binary-interpolative-coding">Binary Interpolative Coding</a></h3>
<p>Binary Interpolative Coding (BIC) directly encodes a monotonically
increasing sequence. At each step of this recursive algorithm, the
middle element <em>m</em> is encoded by a number <em>m − l − p</em>, where <em>l</em> is the
lowest value and <em>p</em> is the position of <em>m</em> in the currently encoded
sequence. Then we recursively encode the values to the left and right of
<em>m</em>. BIC encodings are very space-efficient, particularly on clustered
data; however, decoding is relatively slow.</p>
<p>To compress an index using BIC use the index type <code>block_interpolative</code>.</p>
<blockquote>
<p>Alistair Moffat, Lang Stuiver: Binary Interpolative Coding for Effective Index Compression. Inf. Retr. 3(1): 25-47 (2000)</p>
</blockquote>
<h3 id="elias-fano"><a class="header" href="#elias-fano">Elias-Fano</a></h3>
<p>Given a monotonically increasing integer sequence <em>S</em> of size <em>n</em>, such that \(S_{n-1} &lt; u\), we can encode it in binary using \(\lceil\log u\rceil\) bits.
Elias-Fano coding splits each number into two parts, a low part consisting of \(l = \lceil\log \frac{u}{n}\rceil\) right-most bits, and a high part consisting of the remaining \(\lceil\log u\rceil - l\) left-most bits. The low parts are explicitly written in binary for all numbers, in a single stream of bits. The high parts are compressed by writing, in negative-unary form, the gaps between the high parts of consecutive numbers.</p>
<p>To compress an index using Elias-Fano use the index type <code>ef</code>.</p>
<blockquote>
<p>Sebastiano Vigna. 2013. Quasi-succinct indices. In Proceedings of the sixth ACM international conference on Web search and data mining (WSDM ‘13). ACM, New York, NY, USA, 83-92.</p>
</blockquote>
<h3 id="maskedvbyte"><a class="header" href="#maskedvbyte">MaskedVByte</a></h3>
<blockquote>
<p>Jeff Plaisance, Nathan Kurz, Daniel Lemire, Vectorized VByte Decoding, International Symposium on Web Algorithms 2015, 2015.</p>
</blockquote>
<h3 id="optpfd"><a class="header" href="#optpfd">OptPFD</a></h3>
<blockquote>
<p>Hao Yan, Shuai Ding, and Torsten Suel. 2009. Inverted index compression and query processing with optimized document ordering. In Proceedings of the 18th international conference on World wide web (WWW '09). ACM, New York, NY, USA, 401-410. DOI: https://doi.org/10.1145/1526709.1526764</p>
</blockquote>
<h3 id="partitioned-elias-fano"><a class="header" href="#partitioned-elias-fano">Partitioned Elias Fano</a></h3>
<blockquote>
<p>Giuseppe Ottaviano and Rossano Venturini. 2014. Partitioned Elias-Fano indexes. In Proceedings of the 37th international ACM SIGIR conference on Research &amp; development in information retrieval (SIGIR '14). ACM, New York, NY, USA, 273-282. DOI: https://doi.org/10.1145/2600428.2609615</p>
</blockquote>
<h3 id="qmx"><a class="header" href="#qmx">QMX</a></h3>
<p>Quantities, Multipliers, and eXtractor (QMX) packs as many integers as possible into 128-bit words (Quantities) and stores the selectors (eXtractors) separately in a different stream. The selectors are compressed (Multipliers) with
RLE (Run-Length Encoding).</p>
<p>To compress an index using QMX use the index type <code>block_qmx</code>.</p>
<blockquote>
<p>Andrew Trotman. 2014. Compression, SIMD, and Postings Lists. In Proceedings of the 2014 Australasian Document Computing Symposium (ADCS '14), J. Shane Culpepper, Laurence Park, and Guido Zuccon (Eds.). ACM, New York, NY, USA, Pages 50, 8 pages. DOI: https://doi.org/10.1145/2682862.2682870</p>
</blockquote>
<h3 id="simd-bp128"><a class="header" href="#simd-bp128">SIMD-BP128</a></h3>
<blockquote>
<p>Daniel Lemire, Leonid Boytsov: Decoding billions of integers per second through vectorization. Softw., Pract. Exper. 45(1): 1-29 (2015)</p>
</blockquote>
<h3 id="simple8b"><a class="header" href="#simple8b">Simple8b</a></h3>
<blockquote>
<p>Vo Ngoc Anh, Alistair Moffat: Index compression using 64-bit words. Softw., Pract. Exper. 40(2): 131-147 (2010)</p>
</blockquote>
<h3 id="simple16"><a class="header" href="#simple16">Simple16</a></h3>
<blockquote>
<p>Jiangong Zhang, Xiaohui Long, and Torsten Suel. 2008. Performance of compressed inverted list caching in search engines. In Proceedings of the 17th international conference on World Wide Web (WWW '08). ACM, New York, NY, USA, 387-396. DOI: https://doi.org/10.1145/1367497.1367550</p>
</blockquote>
<h3 id="streamvbyte"><a class="header" href="#streamvbyte">StreamVByte</a></h3>
<blockquote>
<p>Daniel Lemire, Nathan Kurz, Christoph Rupp: Stream VByte: Faster byte-oriented integer compression. Inf. Process. Lett. 130: 1-6 (2018). DOI: https://doi.org/10.1016/j.ipl.2017.09.011</p>
</blockquote>
<h3 id="varint-g8iu"><a class="header" href="#varint-g8iu">Varint-G8IU</a></h3>
<blockquote>
<p>Alexander A. Stepanov, Anil R. Gangolli, Daniel E. Rose, Ryan J. Ernst, and Paramjit S. Oberoi. 2011. SIMD-based decoding of posting lists. In Proceedings of the 20th ACM international conference on Information and knowledge management (CIKM '11), Bettina Berendt, Arjen de Vries, Wenfei Fan, Craig Macdonald, Iadh Ounis, and Ian Ruthven (Eds.). ACM, New York, NY, USA, 317-326. DOI: https://doi.org/10.1145/2063576.2063627</p>
</blockquote>
<h3 id="varintgb"><a class="header" href="#varintgb">VarintGB</a></h3>
<blockquote>
<p>Jeffrey Dean. 2009. Challenges in building large-scale information retrieval systems: invited talk. In Proceedings of the Second ACM International Conference on Web Search and Data Mining (WSDM '09), Ricardo Baeza-Yates, Paolo Boldi, Berthier Ribeiro-Neto, and B. Barla Cambazoglu (Eds.). ACM, New York, NY, USA, 1-1. DOI: http://dx.doi.org/10.1145/1498759.1498761</p>
</blockquote>
<div style="break-before: page; page-break-before: always;"></div><h1 id="wand-data-1"><a class="header" href="#wand-data-1">&quot;WAND&quot; Data</a></h1>
<blockquote>
<p><strong>WARNING</strong> <br />
&quot;WAND data&quot; is a legacy term that may be somewhat misleading. The name
originates from the WAND algorithm, but in fact all <em>scored</em> queries
must use WAND data. This name will likely change in the future to more
accurately reflect its nature, but we still use it now because it is
prevalent throughout the code base.</p>
</blockquote>
<p>This is a file that contains data necessary for scoring documents, such
as:</p>
<ul>
<li>document lengths,</li>
<li>term occurrence counts,</li>
<li>term posting counts,</li>
<li>number of documents,</li>
<li>term max scores,</li>
<li>(optional) term block-max scores.</li>
</ul>
<p>Use <a href="guide/../cli/create_wand_data.html"><code>create_wand_data</code></a> command to build.</p>
<h2 id="quantization"><a class="header" href="#quantization">Quantization</a></h2>
<p>If you quantize your inverted index, then you have to quantize WAND data
as well, using the same number of bits (otherwise, any algorithms that
depend on max-scores will not function correctly).</p>
<h2 id="compression"><a class="header" href="#compression">Compression</a></h2>
<p>You can build your WAND data with score compression. This will store
scores quantized, thus you need to provide the number of quantization
bits. Note that even if you compress your WAND data, you can still use
it with a non-quantized index: the floating point scores will be
calculated (though they will not be identical to the original scores,
as this compression is <em>lossy</em>). If you do use a quantized index, it
must use the same number of bits as WAND data.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="querying"><a class="header" href="#querying">Querying</a></h1>
<p>Now it is possible to query the index. The command <code>queries</code> treats each
line of the standard input (or a file if <code>-q</code> is present) as a separate
query. A query line contains a whitespace-delimited list of tokens.
These tokens are either interpreted as terms (if <code>--terms</code> is defined,
which will be used to resolve term IDs) or as term IDs (if <code>--terms</code> is
not defined). Optionally, a query can contain query ID delimited by a
colon:</p>
<pre><code>      Q1:one two three
      ^^ ^^^^^^^^^^^^^
query ID         terms
</code></pre>
<p>For example:</p>
<pre><code>$ ./bin/queries \
    -e opt \                        # index encoding
    -a and \                        # retrieval algorithm
    -i test_collection.index.opt \  # index path
    -w test_collection.wand \       # metadata file
    -q ../test/test_data/queries    # query input file
</code></pre>
<p>This performs conjunctive queries (<code>and</code>). In place of <code>and</code> other
operators can be used (see <a href="guide/querying.html#query-algorithms">Query algorithms</a>), and
also multiple operators separated by colon (<code>and:or:wand</code>), which will
run multiple passes, one per algorithm.</p>
<p>If the WAND file is compressed, append <code>--compressed-wand</code> flag.</p>
<h2 id="build-additional-data"><a class="header" href="#build-additional-data">Build additional data</a></h2>
<p>To perform BM25 queries it is necessary to build an additional file
containing the parameters needed to compute the score, such as the
document lengths. The file can be built with the following command:</p>
<pre><code>$ ./bin/create_wand_data \
    -c ../test/test_data/test_collection \
    -o test_collection.wand
</code></pre>
<p>If you want to compress the file append <code>--compress</code> at the end of the
command. When using variable-sized blocks (for VBMW) via the
<code>--variable-block</code> parameter, you can also specify lambda with the <code>-l &lt;float&gt;</code> or <code>--lambda &lt;float&gt;</code> flags. The value of lambda impacts the
mean size of the variable blocks that are output. See the VBMW paper
(listed below) for more details. If using fixed-sized blocks, which is
the default, you can supply the desired block size using the <code>-b &lt;UINT&gt; </code> or <code>--block-size &lt;UINT&gt;</code> arguments.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="retrieval-algorithms"><a class="header" href="#retrieval-algorithms">Retrieval Algorithms</a></h1>
<p>This is the list of the supported query processing algorithms.</p>
<h2 id="unranked"><a class="header" href="#unranked">Unranked</a></h2>
<p>PISA implements two <em>unranked</em> algorithms, meaning they return a full
list of documents matching the query in the order of their appearance in
the posting lists.</p>
<h3 id="intersection"><a class="header" href="#intersection">Intersection</a></h3>
<p>The intersection algorithm (<code>and</code>) returns only the documents that match
all query terms.</p>
<h3 id="union"><a class="header" href="#union">Union</a></h3>
<p>The union algorithm (<code>or</code>) returns all the documents that match any
query term.</p>
<h2 id="top-k-retrieval"><a class="header" href="#top-k-retrieval">Top-k Retrieval</a></h2>
<p>Top-k retrieval returns the top-k highest scored documents with respect
To the given query.</p>
<h3 id="document-at-a-time-daat"><a class="header" href="#document-at-a-time-daat">Document-at-a-time (DaaT)</a></h3>
<p>Document-at-a-time algorithms traverse one document at a time. They rely
on posting lists being sorted by document IDs, and scan them in step to
retrieve all frequencies for a document right away.</p>
<h4 id="conjunctive-processing"><a class="header" href="#conjunctive-processing">Conjunctive processing</a></h4>
<p>Conjunctive processing (<code>ranked_and</code>) returns the top <em>k</em> documents that
contain <em>all</em> of the query terms. This is an exhaustive algorithm,
meaning all documents must be scored.</p>
<h4 id="disjunctive-processing"><a class="header" href="#disjunctive-processing">Disjunctive processing</a></h4>
<p>Conjunctive processing (<code>ranked_or</code>) returns the top <em>k</em> documents that
contain <em>any</em> of the query terms. This is an exhaustive algorithm,
meaning all documents must be scored.</p>
<h4 id="maxscore"><a class="header" href="#maxscore">MaxScore</a></h4>
<p>MaxScore (<code>maxscore</code>) uses precomputed maximum partial scores for each
term to avoid calculating all scores. It is especially suitable for
longer queries (high term count), short posting lists, or high values of
<em>k</em> (number of returned top documents).</p>
<blockquote>
<p>Howard Turtle and James Flood. 1995. Query evaluation: strategies and
optimizations. Inf. Process. Manage. 31, 6 (November 1995), 831-850.
DOI=http://dx.doi.org/10.1016/0306-4573(95)00020-H</p>
</blockquote>
<h4 id="wand"><a class="header" href="#wand">WAND</a></h4>
<p>Similar to MaxScore, WAND (<code>wand</code>) uses precomputed maximum partial
scores for each term to avoid calculating all scores. Its performance is
sensitive to the term count, so it may not be the best choice for long
queries. It may also take a performance hit when <em>k</em> is very high, in
which case MaxScore may prove more efficient.</p>
<blockquote>
<p>Andrei Z. Broder, David Carmel, Michael Herscovici, Aya Soffer, and
Jason Zien. 2003. Efficient query evaluation using a two-level
retrieval process. In Proceedings of the twelfth international
conference on Information and knowledge management (CIKM '03). ACM,
New York, NY, USA, 426-434. DOI: https://doi.org/10.1145/956863.956944</p>
</blockquote>
<h4 id="blockmax-wand"><a class="header" href="#blockmax-wand">BlockMax WAND</a></h4>
<p>BlockMax WAND (<code>block_max_wand</code>) builds on top of WAND. It uses
additional precomputed scores for ranges of documents in posting lists,
which allows for skipping entire blocks of documents if their max score
is low enough.</p>
<blockquote>
<p>Shuai Ding and Torsten Suel. 2011. Faster top-k document retrieval
using block-max indexes. In Proceedings of the 34th international ACM
SIGIR conference on Research and development in Information Retrieval
(SIGIR '11). ACM, New York, NY, USA, 993-1002.
DOI=http://dx.doi.org/10.1145/2009916.2010048</p>
</blockquote>
<h4 id="variable-blockmax-wand"><a class="header" href="#variable-blockmax-wand">Variable BlockMax WAND</a></h4>
<p>Variable BlockMax WAND is the same algorithm as <code>block_max_wand</code> at
query time. The difference is in precomputing the block-max scores.
Instead having even block sizes, each block can have a different size,
to optimize the effectiveness of skips.</p>
<blockquote>
<p>Antonio Mallia, Giuseppe Ottaviano, Elia Porciani, Nicola Tonellotto,
and Rossano Venturini. 2017. Faster BlockMax WAND with Variable-sized
Blocks. In Proceedings of the 40th International ACM SIGIR Conference
on Research and Development in Information Retrieval (SIGIR '17). ACM,
New York, NY, USA, 625-634. DOI:
https://doi.org/10.1145/3077136.3080780</p>
</blockquote>
<h4 id="blockmax-maxscore"><a class="header" href="#blockmax-maxscore">BlockMax MaxScore</a></h4>
<p>BlockMax MaxScore (<code>block_max_maxscore</code>) is a MaxScore implementation
with additional block-max scores, similar to BlockMax WAND.</p>
<h4 id="blockmax-and"><a class="header" href="#blockmax-and">BlockMax AND</a></h4>
<p>BlockMax AND (<code>block_max_ranked_and</code>) is a conjunctive algorithm using
block-max scores.</p>
<h3 id="term-at-a-time-taat"><a class="header" href="#term-at-a-time-taat">Term-at-a-time (TaaT)</a></h3>
<p>Term-at-a-time algorithms traverse one posting list at a time. Thus,
they cannot rely on all frequencies for a given document being known at
the time of their processing. This requires an accumulator structure to
keep partial scores.</p>
<h4 id="disjunctive-taat-processing"><a class="header" href="#disjunctive-taat-processing">Disjunctive TaaT processing</a></h4>
<p>Disjunctive TaaT (<code>ranked_or_taat</code>) is a simple algorithm that
accumulates document scores while traversing postings one list at a
time. <code>ranked_or_taat_lazy</code> is a variant that uses an accumulator array
that initializes lazily.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="document-reordering"><a class="header" href="#document-reordering">Document Reordering</a></h1>
<p>PISA supports reassigning document IDs that were initially assigned in order of parsing.
The point of doing it is usually to decrease the index size or speed up query processing.
This part is done on an uncompressed inverted index.
Depending on the method, you might also need access to some parts of the forward index.
We support the following ways of reordering:</p>
<ul>
<li>random,</li>
<li>by a feature (such as URL or document TREC ID),</li>
<li>with a custom-defined mapping, and</li>
<li>recursive graph bisection.</li>
</ul>
<p>All of the above are supported by a single command <code>reorder-docids</code>.
Below, we explain each method and show some examples of running the command.</p>
<h2 id="reordering-document-lexicon"><a class="header" href="#reordering-document-lexicon">Reordering document lexicon</a></h2>
<p>All methods can optionally take a path to a document lexicon and make a copy of it that reflects
the produced reordering.</p>
<pre><code class="language-bash">reorder-docids \
    --documents /path/to/original/doclex \
    --reordered-documents /path/to/reordered/doclex \
    ...
</code></pre>
<p>Typically, you will want to do that if you plan to evaluate queries, which will need access to
a correct document lexicon.</p>
<blockquote>
<p><strong>NOTE</strong>: Because these options are common to all reordering methods, we ignore them below for brevity.</p>
</blockquote>
<h2 id="random"><a class="header" href="#random">Random</a></h2>
<p>Random document reordering, as the name suggests, randomly shuffles all document IDs.
Additionally, it can take a random seed. Two executions of the command with the same seed
will produce the same final ordering.</p>
<pre><code class="language-bash">reorder-docids --random \
    --collection /path/to/inv \
    --output /path/to/inv.random \
    --seed 123456789 # optional
</code></pre>
<h2 id="by-feature-eg-url-or-trecid"><a class="header" href="#by-feature-eg-url-or-trecid">By feature (e.g., URL or TRECID)</a></h2>
<p>An index can be reordered according to any single document feature, such as URL or TRECID,
as long as it is stored in a text file line by line, where line <code>n</code> is the feature of
document <code>n</code> in the original order.</p>
<p>In particular, our collection parsing command produces two such feature files:</p>
<ul>
<li><code>*.documents</code>, which is typically a list of TRECIDs,</li>
<li><code>*.urls</code>, which is a list of document URLs.</li>
</ul>
<p>To use either, you simply need to run:</p>
<pre><code class="language-bash">reorder-docids \
    --collection /path/to/inv \
    --output /path/to/inv.random \
    --by-feature /path/to/feature/file
</code></pre>
<h2 id="from-custom-mapping"><a class="header" href="#from-custom-mapping">From custom mapping</a></h2>
<p>You can also produce a mapping yourself and feed it to the command.
Such mapping is a text file with two columns separated by a whitespace:</p>
<pre><code>&lt;original ID&gt; &lt;new ID&gt;
</code></pre>
<p>Having that, reordering is as simple as running:</p>
<pre><code class="language-bash">reorder-docids \
    --collection /path/to/inv \
    --output /path/to/inv.random \
    --from-mapping /path/to/custom/mapping
</code></pre>
<h2 id="recursive-graph-bisection"><a class="header" href="#recursive-graph-bisection">Recursive Graph Bisection</a></h2>
<p>We provide an implementation of the <em>Recursive Graph Bisection</em> (aka <em>BP</em>) algorithm,
which is currently the state-of-the-art for minimizing the compressed space used
by an inverted index (or graph) through document reordering.
The algorithm tries to minimize an objective function directly related to the number
of bits needed to store a graph or an index using a delta-encoding scheme.</p>
<p>Learn more from the original paper:</p>
<blockquote>
<p>L. Dhulipala, I. Kabiljo, B. Karrer, G. Ottaviano, S. Pupyrev, and A. Shalita.
Compressing  graphs  and  indexes  with  recursive  graph  bisection.
In Proc. SIGKDD, pages 1535–1544, 2016.</p>
</blockquote>
<p>In PISA, you simply need to pass <code>--recursive-graph-bisection</code> option (or its alias <code>--bp</code>)
to the <code>reorder-docids</code> command.</p>
<pre><code class="language-bash">reorder-docids --bp \
    --collection /path/to/inv \
    --output /path/to/inv.random
</code></pre>
<p>Note that <code>--bp</code> allows for some additional options.
For example, the algorithm constructs a forward index in memory, which is in a special format
<strong>separate from the PISA forward index</strong> that you obtain from the <code>parse_collection</code> tool.
You can instruct <code>reorder-docids</code> to store that intermediate structure (<code>--store-fwdidx</code>),
as well as provide a previously constructed one (<code>--fwdidx</code>), which can be useful if you
want to reuse it for several runs with different algorithm parameters.
To see all available parameters, run <code>reorder-docids --help</code>.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="sharding"><a class="header" href="#sharding">Sharding</a></h1>
<p>We support partitioning a collection into a number of smaller subsets called <em>shards</em>.
Right now, only a forward index can be partitioned by running <code>partition_fwd_index</code> command.
For convenience, we provide <code>shards</code> command that supports certain bulk operations on all shards.</p>
<h2 id="partitioning-collection"><a class="header" href="#partitioning-collection">Partitioning collection</a></h2>
<p>We support two methods of partitioning: random, and by a defined mapping.
For example, one can partition collection randomly:</p>
<pre><code>$ partition_fwd_index \
    -j 8 \                          # use up to 8 threads at a time
    -i full_index_prefix \
    -o shard_prefix \
    -r 123                          # partition randomly into 123 shards
</code></pre>
<p>Alternatively, a set of files can be provided.
Let's assume we have a folder <code>shard-titles</code> with a set of text files.
Each file contains new-line-delimited document titles (e.g., TREC-IDs) for one partition.
Then, one would call:</p>
<pre><code>$ partition_fwd_index \
    -j 8 \                          # use up to 8 threads at a time
    -i full_index_prefix \
    -o shard_prefix \
    -s shard-titles/*
</code></pre>
<p>Note that the names of the files passed with <code>-s</code> will be ignored.
Instead, each shard will be assigned a numerical ID from <code>0</code> to <code>N - 1</code> in order
in which they are passed in the command line.
Then, each resulting forward index will have appended <code>.ID</code> to its name prefix:
<code>shard_prefix.000</code>, <code>shard_prefix.001</code>, and so on.</p>
<h2 id="working-with-shards"><a class="header" href="#working-with-shards">Working with shards</a></h2>
<p>The <code>shards</code> tool allows to perform some index operations in bulk on all shards at once.
At the moment, the following subcommands are supported:</p>
<ul>
<li>invert,</li>
<li>compress,</li>
<li>wand-data, and</li>
<li>reorder-docids.</li>
</ul>
<p>All input and output paths passed to the subcommands will be expanded for each individual shards
by extending it with <code>.&lt;shard-id&gt;</code> (e.g., <code>.000</code>) or, if substring <code>{}</code> is present, then
the shard number will be substituted there. For example:</p>
<pre><code class="language-bash">shards reorder-docids --by-url \
    -c inv \
    -o inv.url \
    --documents fwd.{}.doclex \
    --reordered-documents fwd.url.{}.doclex
</code></pre>
<p>is equivalent to running the following command for every shard <code>XYZ</code>:</p>
<pre><code class="language-bash">reorder-docids --by-url \
    -c inv.XYZ \
    -o inv.url.XYZ \
    --documents fwd.XYZ.doclex \
    --reordered-documents fwd.url.XYZ.doclex
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="threshold-estimation"><a class="header" href="#threshold-estimation">Threshold Estimation</a></h1>
<p>Currently it is possible to perform threshold estimation tasks using the
<code>kth_threshold</code> tool. The tool computes the k-highest impact score for
each term of a query. Clearly, the top-k threshold of a query can be
lower-bounded by the maximum of the k-th highest impact scores of the
query terms.</p>
<p>In addition to the k-th highest score for each individual term, it is
possible to use the k-th highest score for certain pairs and triples of
terms.</p>
<p>To perform threshold estimation use the <code>kth_threshold</code> command.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="regression-test-for-robust04"><a class="header" href="#regression-test-for-robust04">Regression test for Robust04</a></h1>
<p>This tutorial explains how to run regression tests on the <a href="https://trec.nist.gov/data/t13_robust.html">Robust04</a>
collection.</p>
<h2 id="requirements-1"><a class="header" href="#requirements-1">Requirements</a></h2>
<p>Due to the collection's license, we cannot distribute it, and thus you
will need to obtain it separately to run this test. See
https://trec.nist.gov/data/cd45/index.html for more information.</p>
<h2 id="docker-image"><a class="header" href="#docker-image">Docker Image</a></h2>
<p>In the repository, we provide a Docker image definition under
<code>test/docker/benchmark</code> to make reproducing results easier. First, to
build the image, run the following command from the repository's root
directory:</p>
<pre><code>docker build -t pisa-bench -f- .. &lt; test/docker/benchmark/Dockerfile
</code></pre>
<p>You can use any name instead of <code>pisa-bench</code> but if you use a different
one, make sure to substitute it in any subsequent command.</p>
<p>Building the image may take a while because the tools will be compiled.</p>
<p>Once the image is built, you can run it with:</p>
<pre><code>podman run -v path/to/disk45:/opt/disk45:ro -v your/workdir:/opt/workdir --rm pisa-bench
</code></pre>
<p>Replace <code>path/to/disk45</code> with your local path to the Robust04 disk 4 &amp; 5
directory, and <code>your/workdir</code> with the path to a local working
directory, where artifacts will be written.</p>
<p>By default, the script will build all indices and run evaluation. If you
want to inspect the image or run some custom commands, you can execute
the image interactively:</p>
<pre><code>podman run -v $HOME/data/disk45:/opt/disk45:ro -v $HOME/workdir:/opt/workdir \
    --rm -it pisa-bench /bin/bash
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="compress_inverted_index"><a class="header" href="#compress_inverted_index"><code>compress_inverted_index</code></a></h1>
<h2 id="usage"><a class="header" href="#usage">Usage</a></h2>
<pre><code>Compresses an inverted index
Usage: ../../../build/bin/compress_inverted_index [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -c,--collection TEXT REQUIRED
                              Uncompressed index basename
  -o,--output TEXT REQUIRED   Output inverted index
  --check                     Check the correctness of the index
  -e,--encoding TEXT REQUIRED Index encoding
  -w,--wand TEXT Needs: --scorer
                              WAND data filename
  -s,--scorer TEXT Needs: --wand --quantize
                              Scorer function
  --bm25-k1 FLOAT Needs: --scorer
                              BM25 k1 parameter.
  --bm25-b FLOAT Needs: --scorer
                              BM25 b parameter.
  --pl2-c FLOAT Needs: --scorer
                              PL2 c parameter.
  --qld-mu FLOAT Needs: --scorer
                              QLD mu parameter.
  --quantize UINT Needs: --scorer
                              Quantizes the scores using this many bits
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
</code></pre>
<h2 id="description"><a class="header" href="#description">Description</a></h2>
<p>Compresses an inverted index from the uncompressed format using one of
the integer encodings.</p>
<h3 id="input"><a class="header" href="#input">Input</a></h3>
<p>The input to this command is an uncompressed version of the inverted
index <a href="cli/../guide/inverting.html#inverted-index-format">described here</a>.
The <code>--collection</code> option takes the <em>basename</em> of the uncompressed
index.</p>
<h3 id="encoding"><a class="header" href="#encoding">Encoding</a></h3>
<p>The postings are compressed using one of the available integer
encodings, defined by <code>--encoding</code>. The available encoding values are:</p>
<ul>
<li><code>block_interpolative</code>: <a href="cli/../guide/compressing.html#binary-interpolative-coding">Binary Interpolative
Coding</a></li>
<li><code>ef</code>: <a href="cli/../guide/compressing.html#elias-fano">Elias-Fano</a></li>
<li><code>block_maskedvbyte</code>: <a href="cli/../guide/compressing.html#maskedvbyte">MaskedVByte</a></li>
<li><code>block_optpfor</code>: <a href="cli/../guide/compressing.html#optpfd">OptPForDelta</a></li>
<li><code>pef</code>: <a href="cli/../guide/compressing.html#partitioned-elias-fano">Partitioned
Elias-Fano</a></li>
<li><code>block_qmx</code>: <a href="cli/../guide/compressing.html#qmx">QMX</a></li>
<li><code>block_simdbp</code>: <a href="cli/../guide/compressing.html#simd-bp128">SIMD-BP128</a></li>
<li><code>block_simple8b</code>: <a href="cli/../guide/compressing.html#simple8b">Simple8b</a></li>
<li><code>block_simple16</code>: <a href="cli/../guide/compressing.html#simple16">Simple16</a></li>
<li><code>block_streamvbyte</code>: <a href="cli/../guide/compressing.html#streamvbyte">StreamVByte</a></li>
<li><code>block_varintg8iu</code>: <a href="cli/../guide/compressing.html#varint-g8iu">Varint-G8IU</a></li>
<li><code>block_varintgb</code>: <a href="cli/../guide/compressing.html#varintgb">Varint-GB</a></li>
</ul>
<h3 id="precomputed-quantized-scores"><a class="header" href="#precomputed-quantized-scores">Precomputed Quantized Scores</a></h3>
<p>At the time of compressing the index, you can replace frequencies with
quantized precomputed scores. To do so, you must define <code>--quantize</code>
flag, plus some additional options:</p>
<ul>
<li><code>--scorer</code>: scoring function that should be used in to calculate the
scores (<code>bm25</code>, <code>dph</code>, <code>pl2</code>, <code>qld</code>)</li>
<li><code>--wand</code>: metadata filename path</li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><h1 id="compute_intersection"><a class="header" href="#compute_intersection">compute_intersection</a></h1>
<h2 id="usage-1"><a class="header" href="#usage-1">Usage</a></h2>
<pre><code>Computes intersections of posting lists.
Usage: ../../../build/bin/compute_intersection [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -e,--encoding TEXT REQUIRED Index encoding
  -i,--index TEXT REQUIRED    Inverted index filename
  -w,--wand TEXT REQUIRED     WAND data filename
  --compressed-wand Needs: --wand
                              Compressed WAND data file
  --tokenizer TEXT:{english,whitespace} [english] 
                              Tokenizer
  -H,--html                   Strip HTML
  -F,--token-filters TEXT:{krovetz,lowercase,porter2} ...
                              Token filters
  --stopwords TEXT            Path to file containing a list of stop words to filter out
  -q,--queries TEXT           Path to file with queries
  --terms TEXT                Term lexicon
  --weighted                  Weights scores by query frequency
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
  --combinations              Compute intersections for combinations of terms in query
  --max-term-count,--mtc UINT Needs: --combinations
                              Max number of terms when computing combinations
  --min-query-len UINT        Minimum query length
  --max-query-len UINT        Maximum query length
  --header                    Write TSV header
</code></pre>
<h2 id="description-1"><a class="header" href="#description-1">Description</a></h2>
<p>Computes an intersection of posting lists given by the input queries.</p>
<p>It takes a file with queries and outputs the documents in the
intersection of the posting lists. See <a href="cli/queries.html"><code>queries</code></a> for
more details on the input parameters.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="count-postings"><a class="header" href="#count-postings">count-postings</a></h1>
<h2 id="usage-2"><a class="header" href="#usage-2">Usage</a></h2>
<pre><code>Extracts posting counts from an inverted index.
Usage: ../../../build/bin/count-postings [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -e,--encoding TEXT REQUIRED Index encoding
  -i,--index TEXT REQUIRED    Inverted index filename
  --tokenizer TEXT:{english,whitespace} [english] 
                              Tokenizer
  -H,--html                   Strip HTML
  -F,--token-filters TEXT:{krovetz,lowercase,porter2} ...
                              Token filters
  --stopwords TEXT            Path to file containing a list of stop words to filter out
  -q,--queries TEXT           Path to file with queries
  --terms TEXT                Term lexicon
  --weighted                  Weights scores by query frequency
  --sep TEXT                  Separator string
  --query-id                  Print query ID at the beginning of each line, separated by a colon
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
  --sum                       Sum postings accross the query terms; by default, individual list lengths will be printed, separated by the separator defined with --sep
</code></pre>
<h2 id="description-2"><a class="header" href="#description-2">Description</a></h2>
<p>Extracts posting counts from an inverted index.</p>
<p>It sums up posting counts for each query term after parsing. See
<a href="cli/parse_collection.html"><code>parse_collection</code></a> for more details about parsing options.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="create_wand_data"><a class="header" href="#create_wand_data">create_wand_data</a></h1>
<h2 id="usage-3"><a class="header" href="#usage-3">Usage</a></h2>
<pre><code>Creates additional data for query processing.
Usage: ../../../build/bin/create_wand_data [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -c,--collection TEXT REQUIRED
                              Collection basename
  -o,--output TEXT REQUIRED   Output filename
  --quantize UINT             Quantizes the scores using this many bits
  --compress Needs: --quantize
                              Compress additional data
  -s,--scorer TEXT REQUIRED   Scorer function
  --bm25-k1 FLOAT Needs: --scorer
                              BM25 k1 parameter.
  --bm25-b FLOAT Needs: --scorer
                              BM25 b parameter.
  --pl2-c FLOAT Needs: --scorer
                              PL2 c parameter.
  --qld-mu FLOAT Needs: --scorer
                              QLD mu parameter.
  --range Excludes: --block-size --lambda
                              Create docid-range based data
  --terms-to-drop TEXT        A filename containing a list of term IDs that we want to drop
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
[Option Group: blocks]
   
  [At least 1 of the following options are required]
  Options:
    -b,--block-size UINT Excludes: --lambda --range
                                Block size for fixed-length blocks
    -l,--lambda FLOAT Excludes: --block-size --range
                                Lambda parameter for variable blocks
</code></pre>
<h2 id="description-3"><a class="header" href="#description-3">Description</a></h2>
<p>Creates additional data needed for certain query algorithms.
See <a href="cli/../guide/wand_data.html"><code>&quot;WAND&quot; Data</code></a> for more details.</p>
<p>Refer to <a href="cli/queries.html"><code>queries</code></a> for details about scoring functions.</p>
<h2 id="blocks"><a class="header" href="#blocks">Blocks</a></h2>
<p>Each posting list is divided into blocks, and each block gets a
precomputed max score. These blocks can be either of equal size
throughout the index, defined by <code>--block-size</code>, or variable based on
the lambda parameter <code>--lambda</code>. [TODO: Explanation needed]</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="evaluate_queries"><a class="header" href="#evaluate_queries">evaluate_queries</a></h1>
<h2 id="usage-4"><a class="header" href="#usage-4">Usage</a></h2>
<pre><code>Retrieves query results in TREC format.
Usage: ../../../build/bin/evaluate_queries [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -e,--encoding TEXT REQUIRED Index encoding
  -i,--index TEXT REQUIRED    Inverted index filename
  -w,--wand TEXT REQUIRED     WAND data filename
  --compressed-wand Needs: --wand
                              Compressed WAND data file
  --tokenizer TEXT:{english,whitespace} [english] 
                              Tokenizer
  -H,--html                   Strip HTML
  -F,--token-filters TEXT:{krovetz,lowercase,porter2} ...
                              Token filters
  --stopwords TEXT            Path to file containing a list of stop words to filter out
  -q,--queries TEXT           Path to file with queries
  --terms TEXT                Term lexicon
  --weighted                  Weights scores by query frequency
  -k INT REQUIRED             The number of top results to return
  -a,--algorithm TEXT REQUIRED
                              Query processing algorithm
  -s,--scorer TEXT REQUIRED   Scorer function
  --bm25-k1 FLOAT Needs: --scorer
                              BM25 k1 parameter.
  --bm25-b FLOAT Needs: --scorer
                              BM25 b parameter.
  --pl2-c FLOAT Needs: --scorer
                              PL2 c parameter.
  --qld-mu FLOAT Needs: --scorer
                              QLD mu parameter.
  -T,--thresholds TEXT        File containing query thresholds
  -j,--threads UINT           Number of threads
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
  -r,--run TEXT               Run identifier
  --documents TEXT REQUIRED   Document lexicon
  --quantized                 Quantized scores
</code></pre>
<h2 id="description-4"><a class="header" href="#description-4">Description</a></h2>
<p>Returns results for the given queries. The results are printed in the
TREC format. See <a href="cli/queries.html"><code>queries</code></a> for detailed description of
the input parameters.</p>
<p>To print out the string identifiers of the documents (titles), you must
provide the document lexicon with <code>--documents</code>.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="extract-maxscores"><a class="header" href="#extract-maxscores">extract-maxscores</a></h1>
<h2 id="usage-5"><a class="header" href="#usage-5">Usage</a></h2>
<pre><code>
Extracts max-scores for query terms from an inverted index.

The max-scores will be printed to the output separated by --sep,
which is a tab by default.
Usage: ../../../build/bin/extract-maxscores [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -w,--wand TEXT REQUIRED     WAND data filename
  --compressed-wand Needs: --wand
                              Compressed WAND data file
  --tokenizer TEXT:{english,whitespace} [english] 
                              Tokenizer
  -H,--html                   Strip HTML
  -F,--token-filters TEXT:{krovetz,lowercase,porter2} ...
                              Token filters
  --stopwords TEXT            Path to file containing a list of stop words to filter out
  -q,--queries TEXT           Path to file with queries
  --terms TEXT                Term lexicon
  --weighted                  Weights scores by query frequency
  --sep TEXT                  Separator string
  --query-id                  Print query ID at the beginning of each line, separated by a colon
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
  --quantized                 Quantized scores
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="extract_topics"><a class="header" href="#extract_topics">extract_topics</a></h1>
<h2 id="usage-6"><a class="header" href="#usage-6">Usage</a></h2>
<pre><code>A tool for converting queries from several formats to PISA queries.
Usage: ../../../build/bin/extract_topics [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
  -i,--input TEXT REQUIRED    TREC query input file
  -o,--output TEXT REQUIRED   Output basename
  -f,--format TEXT REQUIRED   Input format
  -u,--unique                 Unique queries
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="invert"><a class="header" href="#invert">invert</a></h1>
<h2 id="usage-7"><a class="header" href="#usage-7">Usage</a></h2>
<pre><code>Constructs an inverted index from a forward index.
Usage: ../../../build/bin/invert [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -i,--input TEXT REQUIRED    Forward index basename
  -o,--output TEXT REQUIRED   Output inverted index basename
  --term-count UINT           Number of distinct terms in the forward index
  -j,--threads UINT           Number of threads
  --batch-size UINT [100000]  Number of documents to process at a time
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="kth_threshold"><a class="header" href="#kth_threshold">kth_threshold</a></h1>
<h2 id="usage-8"><a class="header" href="#usage-8">Usage</a></h2>
<pre><code>A tool for performing threshold estimation using the k-highest impact score for each term, pair or triple of a query. Pairs and triples are only used if provided with --pairs and --triples respectively.
Usage: ../../../build/bin/kth_threshold [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -e,--encoding TEXT REQUIRED Index encoding
  -i,--index TEXT REQUIRED    Inverted index filename
  -w,--wand TEXT REQUIRED     WAND data filename
  --compressed-wand Needs: --wand
                              Compressed WAND data file
  --tokenizer TEXT:{english,whitespace} [english] 
                              Tokenizer
  -H,--html                   Strip HTML
  -F,--token-filters TEXT:{krovetz,lowercase,porter2} ...
                              Token filters
  --stopwords TEXT            Path to file containing a list of stop words to filter out
  -q,--queries TEXT           Path to file with queries
  --terms TEXT                Term lexicon
  --weighted                  Weights scores by query frequency
  -k INT REQUIRED             The number of top results to return
  -s,--scorer TEXT REQUIRED   Scorer function
  --bm25-k1 FLOAT Needs: --scorer
                              BM25 k1 parameter.
  --bm25-b FLOAT Needs: --scorer
                              BM25 b parameter.
  --pl2-c FLOAT Needs: --scorer
                              PL2 c parameter.
  --qld-mu FLOAT Needs: --scorer
                              QLD mu parameter.
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
  -p,--pairs TEXT Excludes: --all-pairs
                              A tab separated file containing all the cached term pairs
  -t,--triples TEXT Excludes: --all-triples
                              A tab separated file containing all the cached term triples
  --all-pairs Excludes: --pairs
                              Consider all term pairs of a query
  --all-triples Excludes: --triples
                              Consider all term triples of a query
  --quantized                 Quantizes the scores
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="lexicon"><a class="header" href="#lexicon">lexicon</a></h1>
<h2 id="usage-9"><a class="header" href="#usage-9">Usage</a></h2>
<pre><code>Build, print, or query lexicon
Usage: ../../../build/bin/lexicon [OPTIONS] SUBCOMMAND

Options:
  -h,--help                   Print this help message and exit
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file

Subcommands:
  build                       Build a lexicon
  lookup                      Retrieve the payload at index
  rlookup                     Retrieve the index of payload
  print                       Print elements line by line
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="map_queries"><a class="header" href="#map_queries">map_queries</a></h1>
<h2 id="usage-10"><a class="header" href="#usage-10">Usage</a></h2>
<pre><code>A tool for transforming textual queries to IDs.
Usage: ../../../build/bin/map_queries [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  --tokenizer TEXT:{english,whitespace} [english] 
                              Tokenizer
  -H,--html                   Strip HTML
  -F,--token-filters TEXT:{krovetz,lowercase,porter2} ...
                              Token filters
  --stopwords TEXT            Path to file containing a list of stop words to filter out
  -q,--queries TEXT           Path to file with queries
  --terms TEXT                Term lexicon
  --weighted                  Weights scores by query frequency
  --sep TEXT                  Separator string
  --query-id                  Print query ID at the beginning of each line, separated by a colon
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="parse_collection"><a class="header" href="#parse_collection">parse_collection</a></h1>
<h2 id="usage-11"><a class="header" href="#usage-11">Usage</a></h2>
<pre><code>parse_collection - parse collection and store as forward index.
Usage: ../../../build/bin/parse_collection [OPTIONS] [SUBCOMMAND]

Options:
  -h,--help                   Print this help message and exit
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  -j,--threads UINT           Number of threads
  --tokenizer TEXT:{english,whitespace} [english] 
                              Tokenizer
  -H,--html                   Strip HTML
  -F,--token-filters TEXT:{krovetz,lowercase,porter2} ...
                              Token filters
  --stopwords TEXT            Path to file containing a list of stop words to filter out
  --config                    Configuration .ini file
  -o,--output TEXT REQUIRED   Forward index filename
  -b,--batch-size INT [100000] 
                              Number of documents to process in one thread
  -f,--format TEXT [plaintext] 
                              Input format

Subcommands:
  merge                       Merge previously produced batch files. When parsing process was killed during merging, use this command to finish merging without having to restart building batches.
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="partition_fwd_index"><a class="header" href="#partition_fwd_index">partition_fwd_index</a></h1>
<h2 id="usage-12"><a class="header" href="#usage-12">Usage</a></h2>
<pre><code>Partition a forward index
Usage: ../../../build/bin/partition_fwd_index [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
  -i,--input TEXT REQUIRED    Forward index filename
  -o,--output TEXT REQUIRED   Basename of partitioned shards
  -j,--threads INT            Thread count
  -r,--random-shards INT Excludes: --shard-files
                              Number of random shards
  -s,--shard-files TEXT ... Excludes: --random-shards
                              List of files with shard titles
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="queries"><a class="header" href="#queries">queries</a></h1>
<h2 id="usage-13"><a class="header" href="#usage-13">Usage</a></h2>
<pre><code>Benchmarks queries on a given index.
Usage: ../../../build/bin/queries [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -e,--encoding TEXT REQUIRED Index encoding
  -i,--index TEXT REQUIRED    Inverted index filename
  -w,--wand TEXT              WAND data filename
  --compressed-wand Needs: --wand
                              Compressed WAND data file
  --tokenizer TEXT:{english,whitespace} [english] 
                              Tokenizer
  -H,--html                   Strip HTML
  -F,--token-filters TEXT:{krovetz,lowercase,porter2} ...
                              Token filters
  --stopwords TEXT            Path to file containing a list of stop words to filter out
  -q,--queries TEXT           Path to file with queries
  --terms TEXT                Term lexicon
  --weighted                  Weights scores by query frequency
  -k INT REQUIRED             The number of top results to return
  -a,--algorithm TEXT REQUIRED
                              Query processing algorithm
  -s,--scorer TEXT REQUIRED   Scorer function
  --bm25-k1 FLOAT Needs: --scorer
                              BM25 k1 parameter.
  --bm25-b FLOAT Needs: --scorer
                              BM25 b parameter.
  --pl2-c FLOAT Needs: --scorer
                              PL2 c parameter.
  --qld-mu FLOAT Needs: --scorer
                              QLD mu parameter.
  -T,--thresholds TEXT        File containing query thresholds
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
  --quantized                 Quantized scores
  --extract                   Extract individual query times
  --safe Needs: --thresholds  Rerun if not enough results with pruning.
</code></pre>
<h2 id="description-5"><a class="header" href="#description-5">Description</a></h2>
<p>Runs query benchmarks.</p>
<p>Executes each query on the given index multiple times, and takes the
minimum of those as the final value. Then, it aggregates statistics
across all queries.</p>
<h2 id="input-1"><a class="header" href="#input-1">Input</a></h2>
<p>This program takes a compressed index as its input along with a file
containing the queries (line by line). Note that you need to specify the
correct index encoding with <code>--encoding</code> option, as this is currently
not stored in the index. If the index is quantized, you must pass
<code>--quantized</code> flag.</p>
<p>For certain types of retrieval algorithms, you will also need to pass
the so-called &quot;WAND file&quot;, which contains some metadata like skip lists
and max scores.</p>
<h2 id="query-parsing"><a class="header" href="#query-parsing">Query Parsing</a></h2>
<p>There are several parameters you can define to instruct the program on
how to parse and process the input queries, including which tokenizer to
use, whether to strip HTML from the query, and a list of token filters
(such as stemmers). For a more comprehensive description, see
<a href="cli/parse_collection.html"><code>parse_collection</code></a>.</p>
<p>You can also pass a file containing stop-words, which will be excluded
from the parsed queries.</p>
<p>In order for the parsing to actually take place, you need to also
provide the term lexicon with <code>--terms</code>. If not defined, the queries
will be interpreted as lists of document IDs.</p>
<h2 id="algorithm"><a class="header" href="#algorithm">Algorithm</a></h2>
<p>You can specify what retrieval algorithm to use with <code>--algorithm</code>.
Furthermore, <code>-k</code> option defined how many results to retrieve for each
query.</p>
<h2 id="scoring"><a class="header" href="#scoring">Scoring</a></h2>
<p>Use <code>--scorer</code> option to define which scoring function you want to use
(<code>bm25</code>, <code>dph</code>, <code>pl2</code>, <code>qld</code>). Some scoring functions have additional
parameters that you may override, see the help message above.</p>
<h2 id="thresholds"><a class="header" href="#thresholds">Thresholds</a></h2>
<p>You can also pass a file with list of initial score thresholds. Any
documents that evaluate to a score below this value will be excluded.
This can speed up the algorithm, but if the threshold is too high, it
may exclude some of the relevant top-k results. If you want to always
ensure that the results are as if the initial threshold was zero, you
can pass <code>--safe</code> flag. It will force to recompute the entire query
<em>without an initial threshold</em> if it is detected that relevant documents
have been excluded. This may be useful if you have mostly accurate
threshold estimates, but still need the safety: even though some queries
will be slower, most will be much faster, thus improving overall
throughput and average latency.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="read_collection"><a class="header" href="#read_collection">read_collection</a></h1>
<h2 id="usage-14"><a class="header" href="#usage-14">Usage</a></h2>
<pre><code>Reads binary collection to stdout.
Usage: ../../../build/bin/read_collection [OPTIONS] [SUBCOMMAND]

Options:
  -h,--help                   Print this help message and exit
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
  -c,--collection TEXT REQUIRED
                              Collection file path.
  --maptext TEXT Excludes: --maplex
                              ID to string mapping in text file format. Line n is the string associated with ID n. E.g., if used to read a document from a forward index, this would be the `.terms` file, which maps term IDs to their string reperesentations.
  --maplex TEXT Excludes: --maptext
                              ID to string mapping in lexicon binary file format. E.g., if used to read a document from a forward index, this would be the `.termlex` file, which maps term IDs to their string reperesentations.

Subcommands:
  entry                       Reads single entry.
  range                       Reads a range of entries.
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="reorder-docids"><a class="header" href="#reorder-docids">reorder-docids</a></h1>
<h2 id="usage-15"><a class="header" href="#usage-15">Usage</a></h2>
<pre><code>Reassigns the document IDs.
Usage: ../../../build/bin/reorder-docids [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -c,--collection TEXT REQUIRED
                              Collection basename
  -o,--output TEXT            Output basename
  --documents TEXT            Document lexicon
  --reordered-documents TEXT Needs: --documents
                              Reordered document lexicon
  --seed UINT Needs: --random Random seed.
  --store-fwdidx TEXT Needs: --recursive-graph-bisection
                              Output basename (forward index)
  --fwdidx TEXT Needs: --recursive-graph-bisection
                              Use this forward index
  -m,--min-len UINT Needs: --recursive-graph-bisection
                              Minimum list threshold
  -d,--depth UINT:INT in [1 - 64] Needs: --recursive-graph-bisection Excludes: --node-config
                              Recursion depth
  --node-config TEXT Needs: --recursive-graph-bisection Excludes: --depth
                              Node configuration file
  --nogb Needs: --recursive-graph-bisection
                              No VarIntGB compression in forward index
  -p,--print Needs: --recursive-graph-bisection
                              Print ordering to standard output
  -j,--threads UINT           Number of threads
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
[Option Group: methods]
   
  [Exactly 1 of the following options is required]
  Options:
    --random Needs: --output    Assign IDs randomly. You can use --seed for deterministic results.
    --from-mapping TEXT         Use the mapping defined in this new-line delimited text file
    --by-feature TEXT           Order by URLs from this file
    --recursive-graph-bisection,--bp
                                Use recursive graph bisection algorithm
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="sample_inverted_index"><a class="header" href="#sample_inverted_index">sample_inverted_index</a></h1>
<h2 id="usage-16"><a class="header" href="#usage-16">Usage</a></h2>
<pre><code>A tool for sampling an inverted index.
Usage: ../../../build/bin/sample_inverted_index [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
  -c,--collection TEXT REQUIRED
                              Input collection basename
  -o,--output TEXT REQUIRED   Output collection basename
  -r,--rate FLOAT REQUIRED    Sampling rate (proportional size of the output index)
  -t,--type TEXT REQUIRED     Sampling type
  --terms-to-drop TEXT        A filename containing a list of term IDs that we want to drop
  --seed UINT                 Seed state
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="selective_queries"><a class="header" href="#selective_queries">selective_queries</a></h1>
<h2 id="usage-17"><a class="header" href="#usage-17">Usage</a></h2>
<pre><code>Filters selective queries for a given index.
Usage: ../../../build/bin/selective_queries [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -e,--encoding TEXT REQUIRED Index encoding
  -i,--index TEXT REQUIRED    Inverted index filename
  --tokenizer TEXT:{english,whitespace} [english] 
                              Tokenizer
  -H,--html                   Strip HTML
  -F,--token-filters TEXT:{krovetz,lowercase,porter2} ...
                              Token filters
  --stopwords TEXT            Path to file containing a list of stop words to filter out
  -q,--queries TEXT           Path to file with queries
  --terms TEXT                Term lexicon
  --weighted                  Weights scores by query frequency
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="shards-1"><a class="header" href="#shards-1">shards</a></h1>
<h2 id="usage-18"><a class="header" href="#usage-18">Usage</a></h2>
<pre><code>Executes commands for shards.
Usage: ../../../build/bin/shards [OPTIONS] SUBCOMMAND

Options:
  -h,--help                   Print this help message and exit
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file

Subcommands:
  invert                      Constructs an inverted index from a forward index.
  reorder-docids              Reorder document IDs.
  compress                    Compresses an inverted index
  wand-data                   Creates additional data for query processing.
  taily-stats                 Extracts Taily statistics from the index and stores it in a file.
  taily-score                 Computes Taily shard ranks for queries. NOTE: as term IDs need to be resolved individually for each shard, DO NOT provide already parsed and resolved queries (with IDs instead of terms).
  taily-thresholds            Computes Taily thresholds.
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="stem_queries"><a class="header" href="#stem_queries">stem_queries</a></h1>
<h2 id="usage-19"><a class="header" href="#usage-19">Usage</a></h2>
<pre><code>A tool for stemming PISA queries.
Usage: ../../../build/bin/stem_queries [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
  -i,--input TEXT REQUIRED    Query input file
  -o,--output TEXT REQUIRED   Query output file
  --stemmer TEXT REQUIRED     Stemmer
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="taily-stats"><a class="header" href="#taily-stats">taily-stats</a></h1>
<h2 id="usage-20"><a class="header" href="#usage-20">Usage</a></h2>
<pre><code>Extracts Taily statistics from the index and stores it in a file.
Usage: ../../../build/bin/taily-stats [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -w,--wand TEXT REQUIRED     WAND data filename
  --compressed-wand Needs: --wand
                              Compressed WAND data file
  -s,--scorer TEXT REQUIRED   Scorer function
  --bm25-k1 FLOAT Needs: --scorer
                              BM25 k1 parameter.
  --bm25-b FLOAT Needs: --scorer
                              BM25 b parameter.
  --pl2-c FLOAT Needs: --scorer
                              PL2 c parameter.
  --qld-mu FLOAT Needs: --scorer
                              QLD mu parameter.
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  -c,--collection TEXT REQUIRED
                              Binary collection basename
  -o,--output TEXT REQUIRED   Output file path
  --config                    Configuration .ini file
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="taily-thresholds"><a class="header" href="#taily-thresholds">taily-thresholds</a></h1>
<h2 id="usage-21"><a class="header" href="#usage-21">Usage</a></h2>
<pre><code>Estimates query thresholds using Taily cut-offs.
Usage: ../../../build/bin/taily-thresholds [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  --tokenizer TEXT:{english,whitespace} [english] 
                              Tokenizer
  -H,--html                   Strip HTML
  -F,--token-filters TEXT:{krovetz,lowercase,porter2} ...
                              Token filters
  --stopwords TEXT            Path to file containing a list of stop words to filter out
  -q,--queries TEXT           Path to file with queries
  --terms TEXT                Term lexicon
  --weighted                  Weights scores by query frequency
  -k INT REQUIRED             The number of top results to return
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --stats TEXT REQUIRED       Taily statistics file
  --config                    Configuration .ini file
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="thresholds-1"><a class="header" href="#thresholds-1">thresholds</a></h1>
<h2 id="usage-22"><a class="header" href="#usage-22">Usage</a></h2>
<pre><code>Extracts query thresholds.
Usage: ../../../build/bin/thresholds [OPTIONS]

Options:
  -h,--help                   Print this help message and exit
  -e,--encoding TEXT REQUIRED Index encoding
  -i,--index TEXT REQUIRED    Inverted index filename
  -w,--wand TEXT REQUIRED     WAND data filename
  --compressed-wand Needs: --wand
                              Compressed WAND data file
  --tokenizer TEXT:{english,whitespace} [english] 
                              Tokenizer
  -H,--html                   Strip HTML
  -F,--token-filters TEXT:{krovetz,lowercase,porter2} ...
                              Token filters
  --stopwords TEXT            Path to file containing a list of stop words to filter out
  -q,--queries TEXT           Path to file with queries
  --terms TEXT                Term lexicon
  --weighted                  Weights scores by query frequency
  -k INT REQUIRED             The number of top results to return
  -s,--scorer TEXT REQUIRED   Scorer function
  --bm25-k1 FLOAT Needs: --scorer
                              BM25 k1 parameter.
  --bm25-b FLOAT Needs: --scorer
                              BM25 b parameter.
  --pl2-c FLOAT Needs: --scorer
                              PL2 c parameter.
  --qld-mu FLOAT Needs: --scorer
                              QLD mu parameter.
  -L,--log-level TEXT:{critical,debug,err,info,off,trace,warn} [info] 
                              Log level
  --config                    Configuration .ini file
  --quantized                 Quantizes the scores
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="lookup-table-format-specification"><a class="header" href="#lookup-table-format-specification">Lookup Table Format Specification</a></h1>
<p>A lookup table is a bidirectional mapping from an index, representing an
internal ID, to a binary payload, such as string. E.g., an <code>N</code>-element
lookup table maps values <code>0...N-1</code> to their payloads. These tables are
used for things like mapping terms to term IDs and document IDs to
titles or URLs.</p>
<p>The format of a lookup table is designed to operate without having to
parse the entire structure. Once the header is parsed, it is possible to
operate directly on the binary format to access the data. In fact, a
lookup table will typically be memory mapped. Therefore, it is possible
to perform a lookup (or reverse lookup) without loading the entire
structure into memory.</p>
<p>The header always begins as follows:</p>
<pre><code>+--------+--------+--------   -+
|  0x87  |  Ver.  |        ... |
+--------+--------+--------   -+
</code></pre>
<p>The first byte is a constant identifier. When reading, we can verify
whether this byte is correct to make sure we are using the correct type
of data structure.</p>
<p>The second byte is equal to the version of the format.</p>
<p>The remaining of the format is defined separately for each version. The
version is introduced in order to be able to update the format in the
future but still be able to read old formats for backwards
compatibility.</p>
<h2 id="v1"><a class="header" href="#v1">v1</a></h2>
<pre><code>+--------+--------+--------+--------+--------+--------+--------+--------+
|  0x87  |  0x01  | Flags  |                    0x00                    |
+--------+--------+--------+--------+--------+--------+--------+--------+
|                                 Length                                |
+--------+--------+--------+--------+--------+--------+--------+--------+
|                                                                       |
|                                Offsets                                |
|                                                                       |
+-----------------------------------------------------------------------+
|                                                                       |
|                                Payloads                               |
|                                                                       |
+-----------------------------------------------------------------------+
</code></pre>
<p>Immediately after the version bit, we have flags byte.</p>
<pre><code> MSB                         LSB
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | W | S |
+---+---+---+---+---+---+---+---+
</code></pre>
<p>The first bit (<code>S</code>) indicates whether the payloads are sorted (1) or not
(0). The second bit (<code>W</code>) defines the width of offsets (see below):
32-bit (0) or 64-bit (1). In most use cases, the cumulative size of the
payloads will be small enough to address it by 32-bit offsets. For
example, if we store words that are 16-bytes long on average, we can
address over 200 million of them. For this many elements, reducing the
width of the offsets would save us over 700 MB. Still, we want to
support 64-bit addressing because some payloads may be much longer
(e.g., URLs).</p>
<p>The rest of the bits in the flags byte are currently not used, but
should be set to 0 to make sure that if more flags are introduced, we
know what values to expect in the older iterations, and thus we can make
sure to keep it backwards-compatible.</p>
<p>The following 5 bytes are padding with values of 0. This is to help with
byte alignment. When loaded to memory, it should be loaded with 8-byte
alignment. When memory mapped, it should be already correctly aligned by
the operating system (at least on Linux).</p>
<p>Following the padding, there is a 64-bit unsigned integer encoding the
number of elements in the lexicon (<code>N</code>).</p>
<p>Given <code>N</code> and <code>W</code>, we can now calculate the byte range of all offsets,
and thus the address offset for the start of the payloads. The offsets
are <code>N+1</code> little-endian unsigned integers of size determined by <code>W</code>
(either 4 or 8 bytes). The offsets are associated with consecutive IDs
from 0 to <code>N-1</code>; the last the <code>N+1</code> offsets points at the first byte
after the last payload. The offsets are relative to the beginning of the
first payload, therefore the first offset will always be 0.</p>
<p>Payloads are arbitrary bytes, and must be interpreted by the software.
Although the typical use case are strings, this can be any binary
payload. Note that in case of strings, they will not be 0-terminated
unless they were specifically stored as such. Although this should be
clear by the fact a payload is simply a sequence of bytes, it is only
prudent to point it out. Thus, one must be extremely careful when using
C-style strings, as their use is contingent on a correct values inserted
and encoded in the first place, and assuming 0-terminated strings may
easily lead to undefined behavior. Thus, it is recommended to store
strings without terminating them, and then interpret them as string
views (such as <code>std::string_view</code>) instead of a C-style string.</p>
<p>The boundaries of the k-th payload are defined by the values of k-th and
(k+1)-th offsets. Note that because of the additional offset that points
to immediately after the last payload, we can read offsets <code>k</code> and <code>k+1</code>
for any index <code>k &lt; N</code> (recall that <code>N</code> is the number of elements).</p>
<p>If the payloads are sorted (S), we can find an ID of a certain payload
with a binary search. This is crucial for any application that requires
mapping from payloads to their position in the table.</p>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->


                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">

            </nav>

        </div>




        <script>
            window.playground_copyable = true;
        </script>


        <script src="elasticlunr.min.js"></script>
        <script src="mark.min.js"></script>
        <script src="searcher.js"></script>

        <script src="clipboard.min.js"></script>
        <script src="highlight.js"></script>
        <script src="book.js"></script>

        <!-- Custom JS scripts -->

        <script>
        window.addEventListener('load', function() {
            window.setTimeout(window.print, 100);
        });
        </script>

    </div>
    </body>
</html>
